package org.meichao.demo.service.algorithms;

import java.util.Arrays;

/**
 * 快速排序-指针交换法
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 1, 3, 4, 8, 5};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void  quickSort(int[] arr,int startIndex,int endIndex){
        //递归结束条件
        if(startIndex > endIndex){
            return;
        }
        //分区&返回从哪个下标开始进行分区
        int partitionIndex = partition(arr, startIndex, endIndex);
        //分成两部分递归排序
        quickSort(arr, startIndex, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, endIndex);
    }

    /**
     * 分区&返回从哪个下标开始进行分区
     * @param arr
     * @param startIndex
     * @param endIndex
     */
    public static int partition(int[] arr,int startIndex,int endIndex){
        //基准元素
        int point = arr[startIndex];
        //数组下标 左指针
        int left = startIndex;
        //数组下标 右指针
        int right = endIndex;
        //循环交换
        while(left != right){
            //控制right指针比较并左移
            while (left < right && point < arr[right]) {
                right--;
            }
            //控制left指针比较并右移
            while (left < right && point >= arr[left]) {
                left++;
            }
            //交换left和right指向的元素
            if (left < right) {
                int tem = arr[right];
                arr[right] = arr[left];
                arr[left] = tem;
            }
        }
        //pivot和指针重合点交换
        int tem = arr[startIndex];
        arr[startIndex] = arr[left];
        arr[left] = tem;
        //返回拆分分区的下标
        return left;
    }




}
